Fermat 素数判定法
$ ^{\forall p\in\N}\left[p\in\mathbb P\Rightarrow\,^{\forall a\in(\Z/p\Z)^*}\left[a^{p-1}\overset p\equiv1\right]\right]
厳密には$ \gcd(a,p)=1でさえあれば$ p<aでも良いが、素数判定の目的からするとどうでも良い
コレの対偶を取ると
$ ^{\forall n\in\N}\left[^{\exist a\in(\Z/n\Z)^*}\left[a^{n-1}\overset n{\not\equiv}1\right]\Rightarrow n\not\in\mathbb P\right]
アルゴリズム
入力: $ n\in\N\quad(n\ge3)
出力: $ nが合成数ならcomposite, さもなくば probably prime
動作
以下を$ k回繰り返す
1. $ a\in[2,n-1]\subset\N を選択
2. $ \gcd(a,n)\ne1なら composite を返す
3. $ a^{n-1}\overset n{\not\equiv}1なら composite を返す
probably prime を返す
評価
ほとんどいかなる$ aを用いても確率的素数と判定される、とも書いてある
運良く$ nと互いに素でない数を引くと gcd を用いた判定の段階で弾けるっぽい